package loengud.w13;

/**
 * Travelling Salesman Problem (TSP).
 *
 * @author A
 *
 */
public class Tsp {

        /**
         * Number of cities to traverse.
         */
        static final int CITIES = 16; // MAX 17
       
        /**
         * Best path found.
         */
        static int[] bestPath;    
       
        /**
         * The length/cost of {@link #bestPath}.
         */
        static int bestlen = Integer.MAX_VALUE;
       
        /**
         * Cities already passed (during iteration).
         */
        static int[] passedCities;
       
        // debug log variables
        static int nodecount = 0, leafcount = 0;
       
        /**
         * City cost data.
         */
        static int[][] data =
                {{0,92,85,178,206,105,121,223,160,12,183,179,26,220,233,184,151,210,224,231,126,216,161,217,178,156,13,131,271,265,89,107,203,90,146,70,224,185,144,183,166,179,244,69,60,247,196,152,156,111,211,43,94,71,36,144,67,123,94},
                {92,0,68,270,298,197,137,213,131,80,250,272,118,245,223,95,243,231,317,323,218,268,72,268,89,147,105,223,261,255,40,171,295,138,57,162,242,206,218,276,77,271,234,161,125,340,265,191,216,84,304,54,159,37,100,237,132,34,158},
                {85,68,0,262,290,189,90,167,84,72,204,235,111,199,177,117,236,184,309,315,210,222,103,221,120,100,97,216,215,209,22,136,258,92,61,154,196,160,190,268,94,228,188,153,93,332,219,145,170,37,296,42,141,60,69,229,117,64,135},
                {178,270,262,0,31,175,219,265,280,190,138,76,152,233,256,347,84,208,158,56,50,168,339,120,356,255,171,66,312,306,266,153,93,189,293,108,237,199,91,9,312,82,285,123,183,73,99,202,196,249,145,221,141,249,204,78,170,300,149},
                {206,298,290,31,0,203,250,296,311,218,170,107,180,264,287,378,118,239,103,25,78,199,367,151,384,286,199,97,343,338,294,185,124,221,325,136,269,231,122,22,344,113,317,151,215,42,130,234,227,280,58,249,172,277,232,106,201,328,181},
                {105,197,189,175,203,0,216,302,256,117,222,176,79,270,293,288,148,260,221,228,123,261,266,214,283,248,98,128,349,343,193,153,200,185,234,67,274,235,152,180,265,176,322,66,140,244,193,202,206,209,208,148,140,176,131,141,162,227,106},
                {121,137,90,219,250,216,0,104,62,119,120,173,136,136,114,152,237,101,309,275,211,138,162,138,179,37,133,154,152,146,96,74,196,30,102,158,133,76,128,228,116,165,125,148,76,292,150,61,86,53,297,121,78,139,85,230,56,124,107},
                {223,213,167,265,296,302,104,0,96,221,149,193,239,32,10,219,310,60,384,322,276,128,239,153,256,71,236,233,48,42,173,149,217,133,179,244,29,67,212,274,183,186,21,234,178,338,165,97,95,130,371,198,162,216,188,304,158,201,196},
                {160,131,84,280,311,256,62,96,0,158,181,233,177,128,106,136,297,124,370,336,271,162,156,186,174,29,172,214,144,138,91,134,257,91,96,215,125,100,189,289,100,226,117,206,137,353,198,122,147,47,357,115,139,133,125,290,117,118,167},
                {12,80,72,190,218,117,119,221,158,0,181,192,38,218,231,172,163,208,237,243,138,214,149,229,166,154,25,143,269,263,76,105,215,89,133,82,223,183,142,196,154,191,242,81,58,260,208,150,154,99,224,31,92,59,34,157,65,110,92},
                {183,250,204,138,170,222,120,149,181,181,0,67,199,117,140,266,183,92,257,195,149,52,276,26,293,156,196,96,196,191,210,80,90,115,216,157,122,84,70,147,229,59,170,170,138,211,38,72,66,167,244,209,94,237,148,177,118,237,128},
                {179,272,235,76,107,176,173,193,233,192,67,0,154,161,184,301,125,136,198,132,90,96,307,48,324,208,173,50,240,235,241,108,24,143,247,112,166,128,58,85,266,8,214,125,157,149,26,131,125,202,185,222,108,250,166,118,137,269,119},
                {26,118,111,152,180,79,136,239,177,38,199,154,0,236,249,210,125,226,199,205,100,232,187,191,204,172,19,105,287,281,115,123,177,106,172,44,240,201,129,158,192,153,260,43,76,222,170,168,172,130,186,69,110,97,52,119,83,149,82},
                {220,245,199,233,264,270,136,32,128,218,117,161,236,0,23,251,278,36,352,289,244,96,270,121,288,103,233,201,79,73,205,117,185,164,211,212,4,35,180,242,215,154,52,202,210,306,133,65,63,162,339,230,130,248,185,272,156,232,164},
                {233,223,177,256,287,293,114,10,106,231,140,184,249,23,0,229,301,51,375,313,267,119,249,144,266,81,246,224,57,51,183,140,208,143,189,235,20,58,203,265,193,177,30,225,188,329,156,88,86,140,362,208,153,226,198,295,168,211,187},
                {184,95,117,347,378,288,152,219,136,172,266,301,210,251,229,0,335,246,408,403,309,284,95,283,112,153,197,282,267,261,95,202,324,157,54,253,248,222,256,356,36,293,241,252,198,420,285,206,232,100,395,141,206,134,173,328,184,62,232},
                {151,243,236,84,118,148,237,310,297,163,183,125,125,278,301,335,0,253,73,121,34,213,312,165,329,272,144,89,357,352,240,176,148,206,281,81,283,245,115,90,311,127,331,96,164,77,144,226,230,255,60,194,163,222,177,7,185,274,130},
                {210,231,184,208,239,260,101,60,124,208,92,136,226,36,51,246,253,0,326,264,219,71,256,95,273,99,223,175,107,101,190,107,159,123,196,203,40,24,154,217,210,129,80,193,164,281,107,54,54,147,313,215,121,233,175,246,145,218,155}};    

//               {{0, 5, 4, 3},              
//                {5, 0, 2, 9},          
//                {4, 2, 0, 6},          
//                {3, 9, 6, 0}};
       
        /**
         * @param args
         */
        public static void main(String[] args) {
                int res;
               
                // log & initialize
                System.out.println("tsp starts ...");              
                passedCities = new int[CITIES];  
                bestPath = new int[CITIES];
               
                // recursive search!
                res = search(0, 0, 0);
               
                // STDOUT results
                System.out.println("min cost: " + bestlen);
                System.out.println("bestpath: ");  
                for (int j = 0; j < CITIES; j++) {
                        System.out.print(" " + bestPath[j]);        
                }
               
                // + statistics
                System.out.println();  
                System.out.println("cities: " + CITIES);
                System.out.println("leafcount: "
                                + leafcount + " nodecount: " + nodecount);  

        } // -main

        /**
         * @param start city to start searching from
         * @param passednr cities passed (recursion term.)
         * @param len
         * @return int
         */
        static int search(int start, int passednr, int len) {
               
                int tmpLen;
                int bestNext;           // best city to go to
                int bestNextLength;     // best city cost

                nodecount++;
                passedCities[passednr] = start;  

                //System.out.println("search: " + start + passednr + len);
                //System.out.print("passed: ");  
                //for (j = 0; j <= passednr; j++) System.out.print(passedcities[j]);  
                //System.out.println("");  

                // all cities passed, terminate recursion!
                if (passednr >= CITIES - 1)  {
                        leafcount++;  
                        len = len + data[start][0];
                       
                        // reset best length + path?
                        if (len < bestlen) {
                                bestlen = len;
                                for (int j = 0; j < CITIES; j++) {
                                        bestPath[j] = passedCities[j];
                                }
                        }
//                      System.out.println("returning len and bestlen: " + len + bestlen);
                       
                        // just return / terminate
                        return len;  
                } // -if
               
                // cities to traverse, find next best
                bestNext = 0;
                bestNextLength = Integer.MAX_VALUE;
                for (int i = 0; i < CITIES; i++) { // city_i
                        // check if it's already traversed?
                        boolean okgo = true;  
                        for (int j = 0; j <= passednr; j++) { // skip?
                                if (passedCities[j] == i) {
                                        okgo = false;
                                        break;            
                                }            
                        } // -for (skip?)
                       
                        // OK
                        if (okgo) {
                                tmpLen = len + data[start][i]; // cost
                                if (tmpLen < bestNextLength) { // better?
                                        bestNextLength = tmpLen;
                                        bestNext = i;  
                                }          
                        } // -if (OK)    
                } // -for (best next city)
               
                // cost of taking only the immediate best next cities
                tmpLen = len + data[start][bestNext];
                if (tmpLen < bestlen) {
                        tmpLen = search(bestNext, passednr + 1, tmpLen); // RECURSION!
                }
               
                // try second best, next cities just in case
                // this will limit the recursion at previous if clause!
                for (int i = 0; i < CITIES; i++) {
                        // skip best next city
                        if (i == bestNext) {
                                continue;  
                        }
                       
                        // traversed?
                        boolean okgo = true;
                        for (int j = 0; j <= passednr; j++) {
                                if (passedCities[j] == i) {
                                        okgo = false;
                                        break;
                                }
                        } // for (traversed?)
                       
                        // OK
                        if (okgo) {
                                tmpLen = len + data[start][i];
                                if (tmpLen < bestlen) {
                                        tmpLen = search(i, passednr + 1, tmpLen); // RECURSION!
                                }
                        } // if (OK)
                } // -for

                return len;    
        } // -search

}
